package luo.hui.jiang.tree;

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;

/**
 * @author 罗惠江
 * @version 1.0
 * @email 1511619294@qq.com
 * @date 2020/8/10 21:34
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[8000000];

        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 80000000);  //生成随机数组
        }

        Instant startTime = Instant.now();
        heapSort(arr);
        Instant endTime = Instant.now(); //获取结束时间
//        System.out.println(Arrays.toString(arr));
        System.out.println(Duration.between(startTime, endTime).toMillis());

    }

    public static void heapSort(int arr[]) {
        int temp = 0;
        System.out.println("堆排序！！！");
        // 第一次先将数组打造成大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        // 形成大顶堆后，我们开始循环操作。
        /**
         * 1.首先将大顶堆的堆顶元素与末尾元素交换，将最大元素沉到数组的末端。
         *
         * 2.重新调整我们结构，使其满足我们堆的定义，然后再执行（1）操作
         */
        for (int i = arr.length - 1; i > 0; i--) {
            // 交换
            temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, i);
        }
    }

    /**
     * 功能：完成 将 以 i 对应的非叶子节点的树调整成为大顶堆
     * 举例 int arr[] = {4,6,8,5,9}; => i=1 => adjustHeap => 得到{4,9,8,5,6}
     * 如果我们再次调用 adjustHeap 传入的是 i = 0 =>得到 {4,9,8,5,6} => {9,6,8,5,4}
     *
     * @param arr    我们调整的数组
     * @param i      要调整的位置
     * @param lenght 需要调整的长度
     */
    public static void adjustHeap(int arr[], int i, int lenght) {
        int temp = arr[i]; // 先取出当前元素的值，保存在临时变量
        // 开始调整
        // 说明
        // 1.k = i * 2 + 1 k 是 i 节点的左子节点
        for (int j = i * 2 + 1; j < lenght; j = j * 2 + 1) {
            // 就是来比较他的左右节点哪个比较大
            if (j + 1 < lenght && arr[j] < arr[j + 1]) {
                j++; // 表示指向他的右边的节点
            }
            if (arr[j] > temp) {   // 如果左右节点中较大的那一个比父节点要大
                arr[i] = arr[j];// 就把较大的那个值赋值给当前节点
                i = j;// ！！！ 别忘了把 值也要赋值回去呀
            } else {
                break;
                // 如果父节点最大，那就不需啊哟进行别的操作了
            }

        }
        // for 循环结束后，我们已经将以 i 为父节点的树的最大值，放在最顶部
        arr[i] = temp; // 将 temp 值放在调整后的位置

    }
}
